Background: Hidden Markov models (HMM) are powerful machine learning toolssuccessfully applied to problems of computational Molecular Biology. In apredictive task, the HMM is endowed with a decoding algorithm in order toassign the most probable state path, and in turn the class labeling, to anunknown sequence. The Viterbi and the posterior decoding algorithms are themost common. The former is very efficient when one path dominates, while thelatter, even though does not guarantee to preserve the automaton grammar, ismore effective when several concurring paths have similar probabilities. Athird good alternative is 1-best, which was shown to perform equal or betterthan Viterbi. Results: In this paper we introduce the posterior-Viterbi (PV) anew decoding which combines the posterior and Viterbi algorithms. PV is a twostep process: first the posterior probability of each state is computed andthen the best posterior allowed path through the model is evaluated by aViterbi algorithm. Conclusions: We show that PV decoding performs better than other algorithmsfirst on toy models and then on the computational biological problem of theprediction of the topology of beta-barrel membrane proteins.
展开▼
